class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        long min_ = min(a, b);
        long ans;
        int lcm_ = lcm(a, b);
        for (long l = 1, r = n * min_, m = 0; l <= r;)
        {
            m = l + ((r - l) >> 1);
            if (m / a + m / b - m / lcm_ >= n)
            {
                ans = m;
                r = m - 1;
            }
            else
                l = m + 1;
        }
        return ans % (long)(1e9 + 7);
    }

    int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }

    int lcm(int a, int b)
    {
        return a * b / gcd(a, b);
    }
};